#include <bits/stdc++.h>
#include "utils.h"


class Sudoku {
private:
    bool isValid(Board<char>& board, int row, int col, char val) {
        for (int i = 0; i < board.size(); i++) {
            if (board[row][i] == val ) return false;
            if (board[i][col] == val ) return false;
            if (board[(row/3)*3 + i/3][(col/3)*3 + i%3] == val) 
                return false;
        }

        // int id = row / 3;
        // int jd = col / 3;
        // for (int i = id*3; i < id*3+3; i++) {
        //     for (int j = jd*3; j < jd*3+3; j++) {
        //         if (board[i][j] == val) return false;
        //     }
        // }

        return true;
    }

    bool backtrack(Board<char>& board, int i, int j) {
        if (i == board.size()) {
            return true;
        }

        if (j == board.size()) {
            return backtrack(board, i + 1, 0);
        }

        if (board[i][j] != '.') {   // 提前已经填好的数字，不管用
            return backtrack(board, i, j+1);
        }

        for(char val = '1'; val <= '9'; val++) {
            if (!isValid(board, i, j, val)) continue;
            board[i][j] = val;
            if (backtrack(board, i, j+1)) return true;
            board[i][j] = '.';
        }
        return false;
    }
public:
    void solveSudoku(Board<char>& board) {
        backtrack(board, 0, 0);
    }
};

int main(int argc, char* argv[]) {
    Sudoku sudoku;
    Board<char> board = {
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'}};

    sudoku.solveSudoku(board);
    prinMat(board);

    return 0;
}